package com.chj.gaoji.class01;

public class Code04_JosephusProblem {

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node josephusKill1(Node head, int m) {
		if (head == null || head.next == head || m < 1) {
			return head;
		}
		Node last = head;
		while (last.next != head) {
			last = last.next;
		}
		int count = 0;
		while (head != last) {
			if (++count == m) {
				last.next = head.next;
				count = 0;
			} else {
				last = last.next;
			}
			head = last.next;
		}
		return head;
	}

	public static Node josephusKill4(Node head, int[] mArr) {
		if (head == null || head.next == head || mArr.length < 1) {
			return head;
		}
		Node last = head;
		while (last.next != head) {
			last = last.next;
		}
		int count = 0;
		int mi = 0;
		while (head != last) {
			if (++count == mArr[mi]) {
				last.next = head.next;
				count = 0;
				if (++mi == mArr.length) {
					mi = 0;
				}
			} else {
				last = last.next;
			}
			head = last.next;
		}
		return head;
	}

	public static Node josephusKill2(Node head, int m) {
		if (head == null || head.next == head || m < 1) {
			return head;
		}
		Node cur = head.next;
		int tmp = 1; // tmp -> list size
		while (cur != head) {
			tmp++;
			cur = cur.next;
		}
		tmp = getLive(tmp, m); // tmp -> service node position
		while (--tmp != 0) {
			head = head.next;
		}
		head.next = head;
		return head;
	}

	// 现在一共有i个节点，数到m就杀死节点，最终会活下来的节点，请返回它在有i个节点时候的编号
	// 旧
	// getLive(N, m)
	public static int getLive(int i, int m) {
//		if (i == 1) {
//			return 1;
//		}
//		return (getLive(i - 1, m) + m - 1) % i + 1;

		int newNum = 1;
		int oldNum = Integer.MIN_VALUE;
		for (int j = 2; j <= i; j++) {
			oldNum = (newNum - 1 + (m - 1) % j + 1) % j + 1;
			newNum = oldNum;
		}

		return oldNum;
	}

	public static void printCircularList(Node head) {
		if (head == null) {
			return;
		}
		System.out.print("Circular List: " + head.value + " ");
		Node cur = head.next;
		while (cur != head) {
			System.out.print(cur.value + " ");
			cur = cur.next;
		}
		System.out.println("-> " + head.value);
	}

	public static Node josephusKill3(Node head, int[] mArr) {
		if (head == null || head.next == head || mArr.length < 1) {
			return head;
		}
		Node cur = head.next;
		int tmp = 1; // tmp -> list size
		while (cur != head) {
			tmp++;
			cur = cur.next;
		}
		tmp = getLiveArr(tmp, mArr); // tmp -> service node position
		while (--tmp != 0) {
			head = head.next;
		}
		head.next = head;
		return head;
	}

//	https://blog.csdn.net/weiainibuqi/article/details/105969284
	public static int getLiveArr(int n, int[] mArr) {
//		if (i == 1) {
//			return 1;
//		}
//		return (getLive(i - 1, m) + m - 1) % i + 1;

		int newNum = 1;
		int oldNum = Integer.MIN_VALUE;
		int m = mArr.length;
		// 推断1个人时，使用的是第几个正整数来淘汰人（num的下标从0开始）
		int k = (n - 1) % m;
		// 推断后面的人那个人被录取（需要推n-1次），因为只有一个人的情况是已知的
		// 从2个人递推到n个人
		for (int i = 2; i <= n; i++) {
			// 因为淘汰人的时候num的下标是正序使用的（0-（m-1）->0）
			// 所以递推谁没有被淘汰时则需要逆序使用num的下标
			// 因为（n-1）是有可能大于m的，所以执行（n-1）次k-1操作k是可能变负数的
			// (k-1+m)加上一个m后对整数的求余结果无影响，
			// 但是对负数而言可以将其挪到正数区间
			k = (k - 1 + m) % m;
			// n个人求职时被录取的那个人，
			// 相对于n-1个人求职时被录取的那个人偏移了num[k]个位置
			oldNum = (newNum - 1 + (mArr[k] - 1) % i + 1) % i + 1;
			newNum = oldNum;
		}

		return oldNum;
	}

	public static Node generateRandomNode(int[] arr) {
		Node head = null;
		Node curr = null;
		for (int i = 0; i < arr.length; i++) {
			Node node = new Node(arr[i]);
			if (i == 0) {
				head = node;
				head.next = head;
				curr = head;
			} else {
				curr.next = node;
				node.next = head;
				curr = node;
			}
		}

		return head;
	}

	public static int[] generateRandomArray(int len, int maxValue) {
		int[] res = new int[len];
		for (int i = 0; i != res.length; i++) {
			res[i] = (int) (Math.random() * maxValue) + (maxValue / 3);
		}
		return res;
	}

	public static int[] copyArray(int[] arr) {
		int[] res = new int[arr.length];
		for (int i = 0; i != res.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

//	https://www.acwing.com/problem/content/description/1457/
//	https://blog.csdn.net/weiainibuqi/article/details/105969284
//	https://www.nowcoder.com/questionTerminal/b28d83bef5414b7f814ae76c66b66ff8?toCommentId=3955610
	public static void main(String[] args) {
		Node head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = head1;
		printCircularList(head1);
		head1 = josephusKill1(head1, 3);
		printCircularList(head1);

		Node head2 = new Node(1);
		head2.next = new Node(2);
		head2.next.next = new Node(3);
		head2.next.next.next = new Node(4);
		head2.next.next.next.next = new Node(5);
		head2.next.next.next.next.next = head2;
		printCircularList(head2);
		head2 = josephusKill2(head2, 3);
		printCircularList(head2);

		Node head3 = null;
		Node curr3 = null;
		int n3 = 8;
		int m3 = 3;
		for (int i = 0; i < n3; i++) {
			Node listNode = new Node(i);
			if (i == 0) {
				head3 = listNode;
				head3.next = head3;
				curr3 = head3;
			} else {
				curr3.next = listNode;
				listNode.next = head3;
				curr3 = listNode;
			}
		}

		printCircularList(head3);
		head3 = josephusKill2(head3, m3);
		printCircularList(head3);

		Node head4 = null;
		Node curr4 = null;
		int n4 = 4;
		int[] m4 = { 3, 1 };
		for (int i = 0; i < n4; i++) {
			Node listNode = new Node(i);
			if (i == 0) {
				head4 = listNode;
				head4.next = head4;
				curr4 = head4;
			} else {
				curr4.next = listNode;
				listNode.next = head4;
				curr4 = listNode;
			}
		}

		printCircularList(head4);
		head4 = josephusKill3(head4, m4);
		printCircularList(head4);

//		printCircularList(head4);
//		head4 = josephusKill4(head4, m4);
//		printCircularList(head4);

		for (int i = 0; i < 1000000; i++) {
			int[] arr = generateRandomArray(50, 500);
			int k = (int) (Math.random() * 20) - 5;
			int[] arr2 = copyArray(arr);
			Node headr1 = generateRandomNode(arr);
			Node headr2 = generateRandomNode(arr2);
			Node headk1 = josephusKill1(headr1, k);
			Node headk2 = josephusKill2(headr2, k);
			if (headk1.value != headk2.value) {
				System.out.println("oops!");
				break;
			}
		}

		System.out.println("111luck!");

		for (int i = 0; i < 1000000; i++) {
			int[] arr = generateRandomArray(50, 500);
			int[] kArr = generateRandomArray(10, 50);
			int[] arr2 = copyArray(arr);
			Node headr1 = generateRandomNode(arr);
			Node headr2 = generateRandomNode(arr2);
			Node headk1 = josephusKill4(headr1, kArr);
			Node headk2 = josephusKill3(headr2, kArr);
			if (headk1.value != headk2.value) {
				System.out.println("oops!");
				break;
			}
		}

		System.out.println("222luck!");
	}

}
